package linkedList.递归;

import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName K个一组翻转链表25.java
 * @Description TODO
 * @createTime 2021年03月08日 20:20:00
 */
public class K个一组翻转链表25 {
    /**
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * <p>
     * k 是一个正整数，它的值小于或等于链表的长度。
     * <p>
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     */

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        K个一组翻转链表25 ii92 = new K个一组翻转链表25();
        ListNode listNode = ii92.reverseKGroup(listNode1, 2);
        System.out.println(listNode);
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode tempHead = head, temp = head;
        //截取k长度的链表
        for (int i = 0; i < k; i++) {
            //如果后面节点不存在则返回头
            if (temp == null) {
                return head;
            } else {
                temp = temp.next;
            }
        }
        //翻转前k个
        ListNode node = reverseList(tempHead, temp);
        //翻转后续
        ListNode group = reverseKGroup(temp, k);
        tempHead.next = group;
        return node;
    }

    private ListNode reverseList(ListNode head, ListNode end) {
        ListNode pre = null, cur = head,next=head;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
